package com.ctrip.study.algorithm.pratice;

import java.util.Stack;

import org.junit.Test;

import junit.framework.TestCase;

/**
 * 反转链表.
 */
public class ReversalLink extends TestCase{
	
	@Test
	public void test(){
		Link link = new Link();
		link.insert(new Node(1));
		link.insert(new Node(2));
		link.insert(new Node(3));
		link.insert(new Node(4));
		link.insert(new Node(5));
		link.insert(new Node(6));
		link.insert(new Node(7));
		System.out.println(link);
		reversalLink(link);
		System.out.println(link);
	}
	
	
	/**
	 * 链表反转.
	 *
	 * @param link the link
	 */
	public void reversalLink(Link link){
		Stack<Node> stack = new Stack<>();
		Node currentNode = link.head;
		while(currentNode != null){
			stack.push(currentNode);
			currentNode = currentNode.next;
		}
		link.head = stack.pop();
		currentNode = link.head;
		while(!stack.empty()){
			Node popNode = stack.pop();
			popNode.next = null;
			currentNode.next = popNode;
			currentNode = popNode;
		}
	}
	
	
	private class Link{
		public Node head;
		public void insert(Node node){
			if(head == null){
				head = node;
			}else{
				Node currentNode = head;
				while(currentNode.next != null){
					currentNode = currentNode.next;
				}
				currentNode.next = node;
			}
		}
		
		public String toString() {
			String display = "";
			Node currentNode = head;
			while(currentNode != null){
				display += currentNode + "--->";
				currentNode = currentNode.next;
			}
			display += "null";
			return display;
		}
	}
	
	private class Node{
		public int data;
		public Node next;
		public Node(int data){
			this.data = data;
		}
		
		@Override
		public String toString() {
			return "Node [data=" + data +"]";
		}
	}

}
